package me.algo.tree;

import java.util.LinkedList;
import java.util.Objects;

/**
 * @author guozheng
 * @date 2024/4/23
 */
public class T11 {
    public static void main(String[] args) {
        int[] ints = {3, 2, 1, 6, 0, 5};
        int maxIndex = maxIndex(ints);
        for (int i : left(ints, maxIndex)) {
            System.out.print(i + ",");
        }
        System.out.println("");
        for (int i : right(ints, maxIndex)) {
            System.out.print(i + ",");
        }

    }

    /**
     * 654. 最大二叉树
     * @param nums
     * @return
     */
    public static TreeNode constructMaximumBinaryTree(int[] nums) {
        if (Objects.isNull(nums) || nums.length == 0) {
            return null;
        }
        int max = maxIndex(nums);
        TreeNode root = new TreeNode(nums[max]);
        LinkedList<Third> stk = new LinkedList<>();
        stk.add(new Third(root, left(nums, max), right(nums, max)));
        while (!stk.isEmpty()) {
            int size = stk.size();
            while (size > 0) {
                size--;
                Third third = stk.removeFirst();
                TreeNode rootNode = third.node;
                int[] leftArr = third.left;
                int[] rightArr = third.right;
                if (Objects.nonNull(leftArr) && leftArr.length != 0) {
                    int lmax = maxIndex(leftArr);
                    TreeNode l = new TreeNode(leftArr[lmax]);
                    rootNode.left = l;
                    int[] left = left(leftArr, lmax);
                    int[] right = right(leftArr, lmax);
                    if (left.length != 0 || right.length != 0) {
                        Third t = new Third(l, left, right);
                        stk.addLast(t);
                    }
                }
                if (Objects.nonNull(rightArr) && rightArr.length != 0) {
                    int rmax = maxIndex(rightArr);
                    TreeNode r = new TreeNode(rightArr[rmax]);
                    rootNode.right = r;
                    int[] left = left(rightArr, rmax);
                    int[] right = right(rightArr, rmax);
                    if (left.length != 0 || right.length != 0) {
                        Third t = new Third(r, left, right);
                        stk.addLast(t);
                    }
                }
            }
        }
        return root;
    }


    record Third(TreeNode node, int[] left, int[] right) {

    }

    static int maxIndex(int[] nums) {
        if (nums.length == 0) {
            return -1;
        }
        int max = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[max]) {
                max = i;
            }
        }
        return max;
    }


    static int[] left(int[] nums, int maxIdx) {
        if (maxIdx == 0) {
            return new int[0];
        }
        int[] rtn = new int[maxIdx];
        for (int i = 0; i < maxIdx; i++) {
            rtn[i] = nums[i];
        }
        return rtn;
    }

    static int[] right(int[] nums, int maxId) {
        int last = nums.length - 1;
        if (maxId == last) {
            return new int[0];
        }
        int[] rtn = new int[last - maxId];
        for (int i = maxId + 1, z = 0; i <= last; i++, z++) {
            rtn[z] = nums[i];
        }
        return rtn;
    }
}
